package com.company.Algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class SimpleMain {

    public static void main(String[] args) {
        System.out.println(arrangeCoins(1804289383));
    }

    // 441.排列硬币
    public static int arrangeCoins(int n) {
        // 暴力破解
//        int length = (int) (Math.sqrt(Integer.MAX_VALUE) * 1.5) + 1;
//        for (int i = 1; i < length; i++) {
//            n -= i;
//            if (n < 0) {
//                return i - 1;
//            } else if (n == 0) {
//                return i;
//            }
//            if (i == length - 1) {
//                System.out.println(n);
//            }
//        }
        // 二分查找

        return 0;
    }

    // 434.字符串的单词数量
    public static int countSegments(String s) {
        int segmentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }

    // 414.第三大的数
    public static int thirdMax(int[] nums) {
        long result = Long.MIN_VALUE, second = Long.MIN_VALUE;
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) {
                if (second > Long.MIN_VALUE) {
                    result = second;
                }
                second = max;
                max = nums[i];
            } else if (nums[i] < max) {
                if (nums[i] > second) {
                    if (second > Long.MIN_VALUE) {
                        result = second;
                    }
                    second = nums[i];
                } else if (nums[i] < second && nums[i] > result) {
                    result = nums[i];
                }
            }
        }
        if (result < Integer.MIN_VALUE) {
            return max;
        }
        return (int) result;
    }

    // 412.fizzBuzz
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                list.add("FizzBuzz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }

    // 409.最长回文串
    public static int longestPalindrome(String s) {
        int length = 0;
        int[] array = new int[128];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            array[ch]++;
        }
        for (int item : array) {
            length += item / 2 * 2;
            if (item % 2 == 1 && length % 2 == 0) {
                length++;
            }
        }
        return length;
    }

    // 189.旋转数组(原地算法)
    public static void rotate(int[] nums, int k) {
        if (k > 0 && nums.length > 1) {
            k = k % nums.length;
            int length = nums.length - 1;
            reverse(nums, 0, length);
            reverse(nums, 0, k - 1);
            reverse(nums, k, length);
        }
    }

    public static void reverse(int[] nums, int start, int end) {
        int temp;
        while (end > start) {
            temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start++;
            end--;
        }
    }


    public static int[] twoSum(int[] numbers, int target) {
        int start = 0, end = numbers.length - 1;
        int[] array = new int[2];

        while (start < end) {
            if (numbers[start] + numbers[end] == target) {
                array[0] = start + 1;
                array[1] = end + 1;
                return array;
            } else if (numbers[start] + numbers[end] > target) {
                end--;
            } else {
                start++;
            }
        }
        return array;
    }

    public static int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                Integer value = hashMap.get(nums[i]) + 1;
                hashMap.put(nums[i], value);
            } else {
                hashMap.put(nums[i], 1);
            }
        }
        for (HashMap.Entry<Integer, Integer> item : hashMap.entrySet()) {
            if (item.getValue() == 1) {
                return item.getKey();
            }
        }
        return 0;
    }

    public static int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max += Math.max(prices[i] - prices[i - 1], 0);
        }
        return max;
    }

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0, minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (minPrice > prices[i]) {
                minPrice = prices[i];
                continue;
            }
            max = Math.max(prices[i] - minPrice, max);
        }
        return max;
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1.length < 1) {
            return;
        }
        int mEnd = nums1.length - 1 - nums2.length, nEnd = nums2.length - 1;
        int index = nums1.length - 1;
        while (index > 0) {
            if (nums1[mEnd] >= nums2[nEnd]) {
                nums1[index] = nums1[mEnd];
                if (mEnd > 0) {
                    mEnd--;
                }

            } else {
                nums1[index] = nums2[nEnd];
                if (nEnd > 0) {
                    nEnd--;
                }

            }

            index--;
        }
    }

    public static int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        int first = 1;
        int second = 2;
        int total = 0;
        for (int i = 2; i < n; i++) {
            total = second + first;
            first = second;
            second = total;
        }
        return total;
    }

    public static int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                return digits;
            } else {
                digits[i] = 0;
            }
        }
        int[] array = new int[digits.length + 1];
        array[0] = 1;
        return array;
    }

    public static int lengthOfLastWord(String s) {
        int length = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                if (length > 0) {
                    break;
                }
                continue;
            }
            length++;
        }
        return length;
    }

    public static int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int max = 0;
        int cur = max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(cur + nums[i], nums[i]);
            max = Math.max(cur, max);
        }

        return max;
    }

    public static int searchInsert(int[] nums, int target) {
        int begin = 0, end = nums.length - 1;
        int balance = end / 2;
        while (begin < end) {
            if (nums[balance] > target) {
                end = balance;
                balance = (end + begin) / 2;
            } else if (nums[balance] < target) {
                begin = balance + 1;
                balance = (end + begin) / 2;

            } else {
                return balance;
            }
        }
        if (nums[balance] < target) {
            balance++;
        }
        return balance;
    }

    public static int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int begin = 0;
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            begin = 0;
            if (haystack.charAt(i) == needle.charAt(begin)) {
                while (begin < needle.length()) {
                    if (haystack.charAt(i + begin) != needle.charAt(begin)) {
                        break;
                    }
                    begin++;
                }
                if (begin == needle.length()) {
                    return i;
                }
            }
        }
        return -1;
    }

    public static int removeElement(int[] nums, int val) {
        int begin = 0, end = nums.length - 1;
        while (begin < end) {
            if (nums[begin] != val) {
                begin++;
                continue;
            }
            while (end > begin && nums[end] == val) {
                end--;
            }
            int temp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = temp;
        }
        return begin + 1;
    }

    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int length = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[length - 1]) {
                nums[length] = nums[i];
                length++;
            }
        }
        return length;
    }

    public static boolean isValid(String s) {
        HashMap<Character, Character> hashMap = new HashMap<>();
        hashMap.put('(', ')');
        hashMap.put('[', ']');
        hashMap.put('{', '}');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (hashMap.containsKey(ch)) {
                stack.push(ch);
                continue;
            }
            if (stack.size() == 0) {
                return false;
            }
            Character pop = stack.pop();
            if (!ch.equals(hashMap.get(pop))) {
                return false;
            }
        }

        return stack.size() == 0;
    }

    public static String longestCommonPrefix(String[] strs) {
        StringBuilder stringBuilder = new StringBuilder();
        int minLength = Integer.MAX_VALUE;
        if (strs.length < 1) {
            return "";
        }
        for (int i = 0; i < strs.length; i++) {
            minLength = Math.min(minLength, strs[i].length());
        }
        for (int i = 0; i < minLength; i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].charAt(i) != ch) {
                    return stringBuilder.toString();
                }
            }
            stringBuilder.append(ch);
        }

        return stringBuilder.toString();
    }

    public static int reverse(int x) {
        int symbol = x < 0 ? -1 : 1;
        int value = Math.abs(x);
        long result = 0;
        while (value > 0) {
            result = result * 10;
            result += value % 10;
            value = value / 10;
        }
        result = result * symbol;
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) result;
    }

    public static boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int num = x;
        int result = 0;
        while (num > 0) {
            result = result * 10;
            result += num % 10;
            num = num / 10;
        }
        return result == x;
    }

    public static String CountAndSay(int n) {
        String endString = "1";
        for (int i = 0; i < n - 1; i++) {
            endString = Build(endString);
        }
        return endString;
    }

    private static String Build(String num) {
        StringBuilder sb = new StringBuilder();
        int count = 1;
        for (int i = 1; i < num.length(); i++) {
            if (num.charAt(i) != num.charAt(i - 1)) {
                sb.append(count);
                sb.append(num.charAt(i - 1));
                count = 0;
            }
            count++;
        }
        sb.append(count);
        sb.append(num.charAt(num.length() - 1));
        return sb.toString();
    }
}
